class Solution {
    public static void main(String[] args) {
        String a = "aabcc" ;
        String b = "dbbca";
        String c = "aadbbcbcac" ;
        System.out.println(isInterleave(a,b,c));
    }
    public static boolean isInterleave(String s1, String s2, String s3) {
            int a = s1.length() , b = s2.length() , c = s3.length() ;
            if(a+b != c) return false ;
            s1 = " " + s1 ;
            s2 = " " + s2 ;
            s3 = " " + s3 ;
            char[] arr1 = s1.toCharArray() ;
            char[] arr2 = s2.toCharArray() ;
            char[] arr3 = s3.toCharArray() ;
            boolean[][] dp = new boolean[a+1][b+1];
            dp[0][0] = true ;
        for(int i = 1 ; i <= a ; i ++){
            if(arr3[i] == arr1[i] && dp[i-1][0]){
                dp[i][0] = true ;
            }
        }
        for(int j = 1 ; j <= b ; j ++){
            if(arr3[j] == arr2[j] && dp[0][j-1]){
                dp[0][j] = true ;
            }
        }
            for(int i=1 ; i <= a ; i ++){
                for(int j=1 ; j <= b ; j ++){
                    if(arr3[i+j] == arr1[i]){
                       dp[i][j] = dp[i-1][j] ;
                    }
                    if(arr3[i+j] == arr2[j]){
                        dp[i][j] = dp[i][j] || dp[i][j-1] ;
                    }
                }
            }
         return dp[a][b] ; 
    }
}